package ljl.alg.jianzhioffer.round1;

/**
 * 求 1+2+...+n ，
 * 要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
 *
 * */
public class Offer64 {
    
    // 这是常用的
    public int sumNums(int n) {
        boolean __ = n > 1 && (n += sumNums(n - 1)) > 0;
        return n;
    }
    
    /**
     * 这种很 tricky 但是省空间，也很快；不过 n 本来就很小，快不了多少
     *
     * n(n+1)/2 除以 2 可以通过位移实现
     * 乘法用俄罗斯农民算法
     *
     * 考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，
     * 其实就是将 B 二进制展开，
     * 如果 B 的二进制表示下第 i 位为 1，那么这一位对最后结果的贡献就是 A*(1<<i) ，即 A<<i。
     * 我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案，
     * 这个方法也被称作「俄罗斯农民乘法」
     * 这个方法经常被用于两数相乘取模的场景，
     *
     * 3 * 6
     * 6: 110
     *
     * +0        3<<1 6
     * +6        3<<2 12
     * +12       3<<3 18
     *
     * = 18
     *
     * 如果两数相乘已经超过数据范围，
     * 但取模后不会超过，
     * 我们就可以利用这个方法来拆位取模计算贡献，保证每次运算都在数据范围内。
     *
     * 下面给出这个算法的 C++ 实现：
     * int quickMulti(int A, int B) {
     *     int ans = 0;
     *     for ( ; B; B >>= 1) {
     *         if (B & 1) {
     *             ans += A;
     *         }
     *         A <<= 1;
     *     }
     *     return ans;
     * }
     *
     * 题目说 n 不大于 10000，最多 14 位，可以循环展开
     *
     * */
    public int sumNums2(int n) {
        int res = 0, a = n, b = n + 1;
        boolean __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        __ = ((b & 1) > 0) && (res += a) > 0; a <<= 1; b >>= 1;
        return res >> 1;
    }
    
}
